//
//  LinkList.hpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/25.
//

#ifndef LinkList_hpp
#define LinkList_hpp

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#endif /* LinkList_hpp */
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

LinkList initLinkList(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}

//头插法新建单链表
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L=initLinkList(L);
    scanf("%d",&x);
    while (x!=9999) {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
    L=initLinkList(L);
    LNode *s,*r=L;
    int x;
    
    scanf("%d",&x);
    while (x!=9999) {
        s=initLinkList(s);
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}
int getLen(LinkList L){
    if (L->next==NULL) {
        return 0;
    }
    int i=1;
    L=L->next;
    while (L->next!=NULL) {
        i++;
        L=L->next;
    }
    return i;
}
//按序号取值
LNode *GetElem(LinkList L,int i){
    int j = 1;
    LinkList p=L->next;
    if (i==0) {
        return L;
    }
    if (i<1) {
        return NULL;
    }
    while (p&&j<i) {
        p=p->next;
        j++;
    }
    return p;
}

//按值查找结点
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while (p!=NULL&&p->data!=e) {
        p=p->next;
    }
    return p;
}

//插入结点
bool LinkList_Insert(LinkList L,int loc,ElemType e){
    if (loc<1||loc>getLen(L)) {
        return false;
    }
    LinkList p=GetElem(L, loc-1);
    LinkList s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//扩展：在某一结点前插入结点
bool LinkList_Insert_before(LinkList L,int loc,ElemType e){
    if (loc<1||loc>getLen(L)) {
        return false;
    }
    LinkList p=GetElem(L, loc-1);
    LinkList s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;     //先插入到它后面，然后再交换数据
    p->next=s;
    ElemType temp=p->data;    //交换数据
    p->data=s->data;
    s->data=temp;
    return true;
}

//删除结点
bool del_lnode(LinkList &L,int loc){
    if (loc<1||loc>getLen(L)) {
        return false;
    }
    LinkList p=GetElem(L, loc-1);
    LinkList q=p->next;
    p->next=q->next;
    free(q);
    return true;
}

//扩展：删除结点也可以先把后继节点的值赋给自己然后删除后继节点

void del_lnode_2(LinkList &L,int loc){
    LinkList p=GetElem(L, loc-1);
    LinkList q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
}

void printlist(LinkList l){
    l=l->next;
    do {
        printf("%d ",l->data);
        l=l->next;
    } while (l);
    printf("\n");
}







